#include<iostream>
namespace MyBBS{
  template<class T>
    class TreeNode{
      public:
      TreeNode(T& date)
        :_left(nullptr)
         ,_right(nullptr)
         ,_parent(nullptr)
         ,_factor(0)
      {
        _date = date;
      }
        TreeNode* _left;
        TreeNode* _right;
        TreeNode* _parent;
        T _date;
        int _factor;
    };
  template<class T>
    class BBSTree{
      public:
      BBSTree():_root(nullptr)
      {}
      BBSTree(T date):_root(new TreeNode<T>(date))
      {}
      void insert(T date)
      {
        //找节点插入位置
        //找空节点（符合搜索树原则）
        if(_root == nullptr)
        {
          _root = new TreeNode<T>(date);
        }
        TreeNode<T>* newnode = new TreeNode<T>(date);
        TreeNode<T>* root = _root;
        TreeNode<T>* parent = nullptr;
        while(root)
        {
          if(newnode->_date > root->_date)
          {
            parent = root;
            root = root->_right;
          }
          else if(newnode->_date < root->_date)
          {
            parent = root;
            root = root->_left;
          }
          else{
            parent = root = nullptr;
            break;
          }
        }
        //插入节点
          if(parent && parent->_date > newnode->_date)
          {
            parent->_left = newnode;
            newnode->_parent = parent;
            parent->_factor--;
            //更新平衡因子，并判断和调整树使其平衡
            _Factor(parent);
          }
          else if(parent && parent->_date < newnode->_date)
          {
            parent->_right = newnode;
            newnode->_parent = parent;
            parent->_factor++;
            //更新平衡因子，并判断和调整树使其平衡
            _Factor(parent);
          }
      }
      void print()
      {
        _print(_root);
      }
      private:
      void _print(TreeNode<T>* root)
      {
        if(root== nullptr)
        {
          return;
        }
        _print(root->_left);
        std::cout << root->_date << " ";
        _print(root->_right);
      }
      void _Factor(TreeNode<T>* parent)
      {
        TreeNode<T>* son = nullptr;
        //更新平衡因子,必要时旋转树
        while(parent)
        {
          if(parent->_factor == 2 || parent->_factor == -2)
          {
            _adjust(parent);
          }
          else if(parent->_factor == 0)
          {
            break;
          }
          else{
            son = parent;
            parent = parent->_parent;
            if(parent && parent->_left == son)
            {
              parent->_factor--;
            }
            else if(parent && parent->_right == son){
              parent->_factor++;
            }
          }
        }
      }
      void _adjust(TreeNode<T>* node)
      {
        if(node->_factor == 2)
        {
          if(node->_right->_factor == 1)
          {
           _leftSpin(node); 
          }
          else if(node->_right->_factor == -1)
          {
            //双旋转
            //先对node->_right进行右旋，将node->_right->_factor = 1
            //再对node进行左旋
            _rightSpin(node->_right);
            _leftSpin(node);
          }
        }
        else{
          if(node->_left->_factor == 1)
          {
            //双旋转
            //先对node->_left进行左旋，将node->_left->_factor = -1
            //再对node进行右旋
            _leftSpin(node->_left);
            _rightSpin(node);
          }
          else if(node->_left->_factor == -1)
          {
            _rightSpin(node);
          }

        }
      }
      //左旋
      void _leftSpin(TreeNode<T>* root)
      {
        TreeNode<T>* left = root->_left;
        TreeNode<T>* right = root->_right;
        TreeNode<T>* Rleft = right->_left;
        //调整左右指针
        right->_left = root;
        root->_right = Rleft;
        //root->_parent左右指针的改变
        if(root->_parent && root->_parent->_left == root)
        {
          root->_parent->_left = right;
        }
        else if(root->_parent && root->_parent->_right == root){
          root->_parent->_right = right;
        }
        //调整_parent指针
        right->_parent = root->_parent;
        root->_parent = right;
        if(Rleft != nullptr)
        Rleft->_parent = root;
        //调整平衡因子
        root->_factor = right->_factor = 0;
        if(left != nullptr)
          left->_factor = 0;
        if(root == _root)
        {
          _root = right;
        }
      }
      //右旋
      void _rightSpin(TreeNode<T>* root)
      {
        TreeNode<T>* left = root->_left;
        TreeNode<T>* right = root->_right;
        TreeNode<T>* Lright = left->_right;
        //调整左右指针
        left->_right = root;
        root->_left = Lright;
        //root->_parent左右指针的改变
        if(root->_parent && root->_parent->_left == root)
        {
          root->_parent->_left = left;
        }
        else if(root->_parent && root->_parent->_right == root){
          root->_parent->_right = left;
        }
        //调整_parent指针
        //调整_parent指针
        left->_parent = root->_parent;
        root->_parent = left;
        if(Lright != nullptr)
        Lright->_parent = root;
        //调整平衡因子
        root->_factor = left->_factor = 0;
        if(right != nullptr)
          right->_factor = 0;
        if(root == _root)
        {
          _root = right;
        }
      }
        TreeNode<T>* _root;
    };
}
